In response to the increasing need for flexibility and speed in integrated circuit (IC) design, a class of IC's known as erasable programmable logic devices (EPLDs) was developed. EPLDs enable the designer to custom program arbitrary logical functions in an IC chip, according relative ease and flexibility in testing prototypes and making design changes.
FIG. 1 illustrates one EPLD architecture which includes an array of function blocks 1, 2, 3, 4 interconnected via a universal interconnect matrix (UIM) 5. For simplicity, only one function block is shown in detail. The input lines 6 into function block 1 are programmably combined into a number of AND gates 7 in an AND array 8. The output lines 9 from AND array 8 are called product terms (or bit lines). Product terms 9 of AND gates 7 are provided to one of a plurality of macrocells (MC) 10 in each function block.
The architecture of a typical macrocell 10 is shown in FIG. 2. Macrocell 10 configures the outputs of AND array 8 of FIG. 1 and may perform additional logic on the output signals of AND array 8. Macrocell 10 contains an OR gate 11 into which product terms are gated, and a register (flip flop) 12 for storing the output signal of OR gate 11. The signals on output line 13 of OR gate 11 and output lines 13a and 13b of register 12 are programmably routed by setting the multiplexers (MUXs) 14, 15 and 16 with configuration bits on their control terminals, each specifying the output state of the respective MUX.
Macrocell 10 advantageously provides a relatively large number of product terms 11.1 per macrocell. However, a fixed product term count is not flexible enough to handle the product term count variability that arises during use of the macrocell. Specifically, user product term requirements for a logic function typically vary widely, anywhere from one to sixteen product terms or more, depending on the complexity of the logic function. In fact, single product term functions are quite common. For logic functions requiring less than eight product terms in macrocell 10, for example, the unused product terms are wasted. For functions requiring more than eight product terms, the function must be split up into two or more subfunctions, each of which can be implemented with the available eight product terms of a macrocell. The results of the subfunction operations must make additional passes through the UIM to be recombined in other macrocells, thus incurring a significant time delay in the execution of complex logic functions.
To address the need for a flexible macrocell architecture, more recent EPLDs feature macrocells with the ability to direct their OR gate output signals directly into adjacent macrocell OR gates, without passing through the interconnect matrix, a feature known as cascading. Cascading enables product terms associated with more than one macrocell to be implemented rapidly, without incurring the delay normally associated with routing signals through the interconnect matrix. This process is known as product term expansion.
Product term expansion is particularly useful during the design of complex integrated circuitry. A serious problem introduced by PLD architectures is that, after device output pin locations are committed (as on a printed circuit board), further alterations of the application logic implemented within the PLD often cannot be accomplished without relocating some of the output pins. The problem of relocation is more prevalent when logic functions have already been formed using product term cascading. Relocation of the output pins results in design delay and expense.
Certain prior art devices provide for the reallocation of product terms by allowing a first cluster of macrocell product terms (e.g., 3 or 4) to be shifted to a first neighboring macrocell and allowing a second cluster of macrocell product terms to be shifted to a second neighboring macrocell. Either all or none of the product terms in the cluster are reallocated. Moreover, each cluster cannot be reallocated beyond its associated neighboring macrocell.
Other prior art devices provide for the reallocation of product terms by providing a path between a series of macrocells. Fixed blocks of four product terms are propagated in a predetermined direction along this path to any one of the macrocells. Yet other devices incorporate macrocells which allow product term expansion without additional passes through macrocell logic. Such macrocells work by "stealing" all the product terms of one or both of its neighboring macrocells, for a total of up to 16 product terms. These macrocells can only "steal" product terms from its immediate neighbors, thereby limiting the flexibility of the macrocells. Moreover, these macrocells are also limited to 16 product terms, and the register within a macrocell whose product terms are stolen is thereby rendered useless.
FIG. 3 shows a macrocell 17 disclosed in Pedersen U.S. Pat. No. 5,121,006. In macrocell 17, cascading is accomplished by setting the configuration bit of MUX 18 to logic 1, thereby directing the signal on output line 19 of OR gate 20 into OR gate 21 of an adjacent macrocell 22. By cascading a series of macrocells in this way, a selectable number of product terms are gated together. For example, OR gate 33 from adjacent macrocell 34 is shown cascaded into OR gate 20 of macrocell 17. The cascading described in Pedersen is unidirectional. If not all of the product terms in macrocell 17 are provided to adjacent macrocell 22, the unused product terms can be routed to the input of exclusive OR gate 36 or to the secondary inputs of register 32. This routing is performed by means of switches 23, 24, 25, 26, 27 and the MUXs 28, 29, 30, 31. The circuit of Pedersen undesirably increases complexity and thus compromises speed. Additionally, macrocell 17 does not provide means for performing an OR operation on the unused product terms.
Other patents which discuss the reallocation of product terms include: U.S. Pat. Nos. 4,758,746 (Birkner et al.); 4,912,345 (Steele et al.); 4,933,577 (Wong et al.); 5,027,011 (Steele); 5,027,315 (Agrawal et al.); 5,136,188 (Ha et al.); 5,260,611 (Cliff et al.) and 5,309,046 (Steele).
Therefore, a need arises for a high speed product term allocation structure that supports the flexible reallocation of product terms among macrocells, even after the device pins have been committed. In particular, a need arises for a product term allocation structure which allows (1) routing of product terms in a bidirectional manner between macrocells, (2) routing of product terms through a plurality of macrocells, (3) routing a variable, selectable number of product terms without a loss of capacity in the macrocell from which the product term is routed, and (4) importing product terms to perform a large function within a local macrocell, while simultaneously exporting product terms from the local macrocell to another macrocell, to maintain the committed pinout during the design phase. None of the above-mentioned documents, nor any combination of the above-mentioned documents, disclose a device which provides these desired advantages.
There is a further need to obtain all of the above described advantages without the concurrent disadvantages of timing, density and pin locking as will be described in greater detail hereinafter.